import java.util.*;

/**
 * Description:
 * User:岁亮亮
 * Date:2024-11-18
 * TIME:17:01
 */
public class MySort {
    public static void timeOutSort(int[] array){
        long start = System.currentTimeMillis();
        MySort.bubbleSort(array);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }
    public static int[] initArray(int[] array){
        int[] temp = new int[array.length];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            temp[i] = random.nextInt(array.length);
        }
        return temp;
    }
    public static void main6(String[] args) {
        List<Integer> list = new ArrayList<Integer>();
        char a = 'b';
        list.add(Integer.valueOf(a));
    }
    public static void main(String[] args) {
        int[] soty = new int[]{2,3,33,1,4,44,33,22,12};
        mergerSortNor(soty);
        System.out.println(Arrays.toString(soty));
    }

    public static void main4(String[] args) {
        int[] soty = new int[]{2,3,33,1,4,44,33,22,12};
        quickSort(soty);
        System.out.println(Arrays.toString(soty));
    }
    public static void main3(String[] args) {
        int[] soty = new int[]{2,3,33,1,4,44,33,22,12};
       selectSort(soty);
        System.out.println(Arrays.toString(soty));
    }
    public static void main2(String[] args) {
        int[] soty = new int[]{2,3,33,1,4,44,33,22,12};
       xierSort(soty);
        System.out.println(Arrays.toString(soty));

    }
    public static void main1(String[] args) {
        int[] soty = new int[]{2,3,33,1,4};
        insertSort(soty);
        System.out.println(Arrays.toString(soty));

    }
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int j = i-1;
            int tmp = array[i];
            while (j >= 0 && array[j] > tmp) {
                array[j+1] = array[j];
                j--;
            }
            array[j+1] = tmp;
        }
    }
    public static void insertSort2(int[] array){
        for(int i = 1; i < array.length;i++){
            int j = i - 1;
            int tmp = array[i];
            while(j >= 0 && array[j] > tmp){
                array[j+1] = array[j];
                j--;
            }
            array[j+1] = tmp;
        }
    }
    public static void xierSort(int[] array){
        int gap = array.length;
        while(gap > 1){
            gap = gap/2;
            insertSort3(array,gap);
        }
    }

    private static void insertSort3(int[] array,int gap) {
        for(int i = gap; i < array.length;i++){
            int j = i - gap ;
            int tmp = array[i];
            while(j >= 0 && array[j] > tmp){
                array[j+gap] = array[j];
                j-=gap;
            }
            array[j+gap] = tmp;
        }
    }
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }

            }
            int tmp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = tmp;

        }
    }
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }

    private static void quick(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = arrayGroup2(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);

    }

    private static int arrayGroup(int[] array, int start, int end) {
        int left = start;
        int right = end;
        while(left < right){
            while(left < right && array[right]>=array[start]){
                right--;
            }
            while(left < right && array[left] <= array[start]){
                left++;
            }

                swap(array,left,right);
        }
        swap(array,start,left);
        return left;
    }
    private static int arrayGroup3(int[] array, int start, int end) {
        int left = start;
        int right = end;
        int tmp = array[start];
        while(left < right){
            while(left < right && array[right]>=tmp){
                right--;
            }
            array[left] = array[right];
            while(left < right && array[left] <= tmp){
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }
    private static int  arrayGroup2(int[] array,int start,int end){
        //数组分组 移动零的思想  数组分为三个区间 0~dest 已处理并且满足条件的
        //dest~cur-1 是不满足条件的 cur ~ length-1是未处理的
        int dest = start;
        int cur = start + 1;
        while(cur <= end){
            if(array[cur] <= array[start] && array[++dest] != array[cur]){
                swap(array,dest,cur);
            }
            cur++;
        }
        swap(array,start,dest);
        return dest;


    }
    private static void swap(int[] array, int left, int right) {
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < array.length - 1 -i; j++) {
                if(array[j] > array[j+1]){
                    flag = true;
                    swap(array,j,j+1);
                }

            }
            if(!flag){
                return;
            }

        }
    }
    public static void quickSort2(int[] array){
        int left = 0;
        int right = array.length - 1;
        Stack<Integer> stack = new Stack<>();
            int pivot = arrayGroup2(array,left,right);
            if(pivot-1 > left){
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot+1 < right){
                stack.push(pivot+1);
                stack.push(right);
            }
            while(!stack.isEmpty()){
                right = stack.pop();
                left = stack.pop();
                pivot = arrayGroup2(array,left,right);
                if(pivot-1 > left){
                    stack.push(left);
                    stack.push(pivot-1);
                }
                if(pivot+1 < right){
                    stack.push(pivot+1);
                    stack.push(right);
                }
            }
        }

    /***
     * 归并排序
     *
     */
    public static void merger(int[] array){
        mergerSort(array,0,array.length-1);
    }

    private static void mergerSort(int[] array, int start, int end) {
        if(start >= end){
            return;
        }
        int mid = (start + end)/2;
        mergerSort(array,start,mid);
        mergerSort(array,mid+1,end);
        //合并
        realMerger(array,start,mid,end);
    }

    private static void realMerger(int[] array, int start, int mid, int end) {
        int left = start;
        int right = end;
        int rel = mid + 1;
        int[] tmp = new int[end - start +1];
        int index = 0;
        while(left <= mid && rel <=right){
           if(array[left] <= array[rel]){
               tmp[index++] = array[left++];
           }
           else{
               tmp[index++] = array[rel++];
           }
        }
        while(left <= mid){
            tmp[index++] = array[left++];
        }
        while(rel <= right){
            tmp[index++] = array[rel++];
        }
       for(int i = 0; i < tmp.length; i++){
           array[start+i] = tmp[i];
       }

    }
    public static void mergerSortNor(int[] array){
        int gap = 1;
        //left mid right
        //
        while(gap < array.length){
            for (int i = 0; i < array.length; i+=gap*2) {
                int left = i;
                int mid = left + gap -1;
                int right = mid + gap;
                if(mid >= array.length || right >= array.length){
                    mid = array.length - 1;
                    right = array.length - 1;
                }
               /* if( right >= array.length){
                    right = array.length - 1;
                }*/
                realMerger(array,left,mid,right);
            }
            gap *= 2;
        }
    }


}
